#include <bits/stdc++.h>
using namespace std;

/*
1792. 最大平均通过率
已解答
中等
相关标签
premium lock icon
相关企业
提示
一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

 

示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。
示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485
 

提示：

1 <= classes.length <= 105
classes[i].length == 2
1 <= passi <= totali <= 105
1 <= extraStudents <= 105
*/

// 法一
class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        // 贪心来简化
        // 最小堆  pq  最小堆→等效最大堆（堆顶为最小负数，对应原提升量最大）
        int n = classes.size();
        priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>>  pq;
        // init
        for (auto &cls : classes) {
            int p = cls[0], t = cls[1];
            // 计算提升量  防止精度损失 1.0 to double
            double gain = (p + 1.0) / (t + 1) - p / (t * 1.0);
            // 负的最小就是正的最大  最小堆
            pq.emplace(-gain, p, t);
        }
        // 分配额外的学生 分配策略 每次都选最大的 （贪心）
        while (extraStudents-- > 0 && !pq.empty()) {
            // 堆顶弹出  就是提升量最大的班级
            auto top = pq.top();
            pq.pop();
            double newGain = get<0>(top);       // 负提升量 用于堆排序
            int p = get<1>(top);
            int t = get<2>(top);
            
            // 班级状态更新
            int new_p = p + 1;
            int new_t = t + 1;
            // 计算更新后的提升量（下次加学生的收益）
            double new_gain = (new_p + 1.0) / (new_t + 1) - new_p / (new_t * 1.0);
            // 重新进堆
            pq.emplace(-new_gain, new_p, new_t);
        }
        // 解决完单一的  现在来看总体
        double total_ratio = 0.0;
        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            int p = get<1>(top);
            int t = get<2>(top);
            total_ratio += p / (t * 1.0); // 计算当前班级的通过率
        }
        // avg
        return total_ratio / n;
    }
};

// 法二
// 优化 
// 思路2 贪心 + 快速旋转 
// 类似 qsort 分区
class Solution {
public:
    // 辅助数据结构
    static const int N = 100005;          // 班级最大数量（预定义常量）
    static constexpr double eps = 1e-8;       // 浮点精度控制（避免精度误差）

    struct node {
        int d; 
        long long b;  // 修复：班级总人数改为long long，避免分配学生后超int上限
        double g; 

        // 边界收益
        void get() {    g = d / ((double)b * (b + 1));  }
        // 排序 其实也可直接lambda里面实现
        bool operator<(const node& A)   const { return g < A.g; } 
    };
    // 所有的非满员班级 p < b 的班级就无需分配学生
    node a[N];

    // 在收益系数阈值y下，班级(i)最多可分配的学生数t
    // 推导t的上限，确保分配t个学生后，边际收益仍≥y（贪心选择高收益分配）
    inline long long func(int d, long long b, double y) {  // 修复：参数b和返回值改为long long
        // t的最大值满足 d/( (b+t)*(b+t+1) ) ≥ y → 解二次不等式得此公式
        return (long long)(sqrt(d * y + 0.25) - b + 0.5 + eps); 
    }

    // 用快速选择分区，批量分配学生
    // a: 待分配班级数组, n: 班级数量, r: 剩余待分配学生数
    void find(node* a, int n, long long r) {  // 修复：剩余学生数r改为long long，避免下溢
        if (r == 0) return;  // 剩余学生为0，终止分配

        // 找选择基准  g 来分区
        int mid_idx = rand() % n;       // 防止最坏情况
        double base_g = a[mid_idx].g;
        int i = 0, j = n - 1;
        // 分区
        do {
            // 左半区
            while (a[i].g < base_g)     ++i;
            while (a[j].g > base_g)     --j;  // 修复：笔误a[i]→a[j]，避免死循环导致溢出
            // swap
            if (i <= j) {
                swap(a[i], a[j]);
                ++i;
                --j;
            }
        } while(i <= j);

        // 分区之后的 最终位置
        mid_idx = i - 1;  // 分区后，基准所在的最终位置（右半区起始前）
        double y = 1.0 / base_g;  // 收益系数阈值（转换为便于计算t的形式）

        // 计算右半区（高收益班级）可分配的总学生数s
        long long s = 0;
        for (int k = mid_idx + 1; k < n; ++k) {
            s += func(a[k].d, a[k].b, y);    // 每个高收益班级最多可分配t个学生
        }

        // 批量分配
        if (s >= r) {  // 右半区可容纳所有剩余学生→递归处理右半区（继续细分高收益）
            find(a + mid_idx + 1, n - mid_idx - 1, r);
        } else {
            // 先填满右半区 剩余的就递归左半区
            for (int k = mid_idx + 1; k < n; ++k) {
                long long t = func(a[k].d, a[k].b, y);  // 修复：t改为long long
                a[k].b += t;  // 总人数增加t
                r -= t;       // 剩余学生减少t
                a[k].get();   // 更新分配后的边际收益系数g
            }
            // 特殊情况：只剩1个班级时，直接分配剩余所有学生（避免递归死循环）
            if (n == 1) {
                a[0].b += r;
                r = 0;
                a[0].get();
            }
            // 递归处理左半区（低收益班级）
            find(a, n, r);
        }
    }

    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        int n = 0;  // 非满员班级数量（p < b的班级）
        double ans = 0.0;
        // 只保留非满员班级（满员班级通过率100%，无需分配学生）
        for (auto& cls : classes) {
            int p = cls[0], b_int = cls[1];
            if (p != b_int) {  // 非满员班级
                a[n].d = b_int - p;  // 未通过人数=总人数-通过人数
                a[n].b = b_int;       // 当前总人数（转为long long）
                a[n].get();       // 计算初始边际收益系数g
                ++n;
            }
        }
        if (n == 0) return 1.0;  // 所有班级满员→平均通过率100%
        // 递归分配所有额外学生（extraStudents转为long long传入）
        find(a, n, (long long)extraStudents);

        // 计算最终平均通过率
        // 总通过率 = 班级数 - 所有非满员班级的"未通过率之和"（未通过率=d/b）
        for (int i = 0; i < n; ++i) {
            ans -= (double)a[i].d / a[i].b;  // 累加未通过率（负号用于后续计算）
        }
        // 平均通过率 = (总班级数 - 未通过率之和) / 总班级数 = 1 - (未通过率之和/总班级数)
        return 1.0 + ans / classes.size();
    }
};